#include <stdio.h>
#include <stdlib.h>
#include "Sort.h"


//冒泡排序
void BubbleSort(int arr[],int len)
{
    //使用标志位flag 表示该趟比较有无交换元素
    int flag;
    for(int i=0; i<len-1; i++)
    {
        flag = 0;
        for(int j=0; j<len-i-1; j++)
        {
            //如果前面的元素大于后面的元素，交换这两个元素
            if(arr[j]>arr[j+1])
            {
                int temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
                flag = 1;
            }
        }
        //如果flag为0，表示数组已经有序，不需要再进行交换
        if(flag == 0)
        {
            break;
        }
    }
}

//选择排序
void SelectSort(int arr[],int len)
{
    int temp;
    for(int i=0; i<len; i++)
    {
        //先把未排序的第一个元素拟为最小值
        temp = i;
        for(int j=i+1; j<len; j++)
        {
            //如果之前最小的元素大于后面的某个元素，将位置更新为更小的值
            if(arr[j]<arr[temp])
            {
                temp=j;
            }
        }
        //把未排序的第一个元素和找到的最小值进行交换 如果第一个元素就是最小值 就不交换了
        if(i!=temp)
        {
            int tem = arr[i];
            arr[i] = arr[temp];
            arr[temp] = tem;
        }
    }
}

//插入排序
void InsertSort(int arr[], int len)
{
    int j,key;
    //从第二个元素向前开始排序
    for (int i=1; i<len; i++)
    {
        //把该元素存下来
        key = arr[i];
        j=i-1;
        //从后往前挪动元素，直到前面的元素比该需要排序的元素小或者等于结束挪动
        while((j>=0) && (arr[j]>key))
        {
            //依次把前面的元素向后移动一位
            arr[j+1] = arr[j];
            j--;
        }
        //此时赋值给空缺出来的数组位置
        arr[j+1] = key;
    }
}

//希尔排序
void ShellSort(int arr[], int length)
{
    int k;
    int temp;	//希尔排序是在插入排序的基础上实现的,所以仍然需要变量来缓存数据
    //对于分组的步长 第一个分组是 长度/2的分组
    //后续分组长度都是前一个分组长度的一半
    //gap是分组的距离 该循环调整分组的距离
    for(int gap=length/2; gap>0; gap=gap/2)
    {
        //遍历每一个分组 得到分组的第一个元素的位置
        for(int i=0; i<gap; i++)
        {
            //遍历出该分组的每一个元素的位置
            for(int j=i; j<length; j=j+gap)
            {
                //对该分组进行单独一次的插入排序
                if(arr[j] < arr[j - gap])
                {
                    temp = arr[j];	//存入缓存数据
                    k = j - gap;
                    while(k>=0 && arr[k]>temp)
                    {
                        arr[k + gap] = arr[k];
                        k = k - gap;
                    }
                    arr[k + gap] = temp;
                }
            }
        }
    }
}












//通过指针交换两个数
void swap(int *x, int *y) 
{
    int t = *x;
    *x = *y;
    *y = t;
}

//三数取中
int GetMid(int *a, int begin, int end)
{
    int mid = (begin + end) >> 2;
    if(a[begin] > a[end])
    {
        if(a[end] > a[mid])
            return end;
        else if(a[mid] > a[begin])
            return begin;
        else
            return mid;
    }
    else
    {
        if(a[end] < a[mid])
            return end;
        else if(a[mid] < a[begin])
            return begin;
        else
            return mid;  
    }
}

//快速排序(挖坑法)
void QuickSort(int *a, int begin, int end) 
{
   if(begin >= end)
      return;

    int mid = GetMid(a, begin, end);
    swap(&a[mid], &a[begin]);
    
    int key = a[begin];
    int pivot = begin;
    int left = begin;
    int right = end;

    while(left < right)
    {
        while(left < right && a[right] >= key)
           right--;
        a[pivot] = a[right];
        pivot = right;

        while(left < right && a[left] <= key)
            left++;
        a[pivot] = a[left];
        pivot = left;
    }

    a[pivot] = key;  

    QuickSort(a, begin, pivot-1);
    QuickSort(a, pivot+1, end);
}

//快速排序(前后指针法)
void QuickSort_Pointer(int *arr, int begin, int end) 
{
    if(begin >= end)
      return;

    //数据区间小于等于10 ，采用插入排序(小区间优化)
    if(end - begin + 1 <= 10)
        InsertSort(arr, end - begin + 1);

    int mid = GetMid(arr, begin, end);
    swap(&arr[mid], &arr[begin]);

    int prev = begin;
    int keyi = begin;
    int cur = begin + 1;

    while(cur <= end)
    {
        //cur一直往前走，如果碰到小于并且prev++不等于cur则交换，
        //因为如果prev+1 == cur 则会发生自己与自己交换的情况
        if(arr[cur] < arr[keyi] && ++prev != cur)
            swap(&arr[cur], &arr[prev]);
        cur++;
    }  
    swap(&arr[prev], &arr[keyi]);
    keyi = prev;

    QuickSort_Pointer(arr, begin, keyi-1);
    QuickSort_Pointer(arr, keyi+1, end);
}










